/*
 *https://leetcode.cn/problems/kth-missing-positive-number/
 *1539. 第 k 个缺失的正整数
 *medium 吴朝泽 2024.9.15
 *二分查找
先处理特殊情况，即数组 arr 中的最小值大于 k。
此时，1 到 k 的所有整数都缺失，因此第 k 个缺失的正整数就是 k。
arr[mid] - mid - 1 计算到索引 mid 为止缺失的整数数量。这里的计算是根据数组元素值和其索引之差来得出的。
二分查找完成后，l 是缺失数量至少为 k 的位置。最终结果通过以下公式计算：
arr[l - 1]：l 之前的索引的值。
k - (arr[l - 1] - (l - 1) - 1)：调整计算以找到第 k 个缺失的正整数。
*/

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if(arr[0] > k)   return k;
        int l = 0, r = arr.size();
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(arr[mid] - mid - 1 >= k)   r = mid;
            else   l = mid + 1;
        }
        return arr[l - 1] + k - (arr[l - 1] - (l - 1) - 1);
    }
};